import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class TestDemo {

    class MinStack {

        private Stack<Integer> stack = new Stack<>();
        private Stack<Integer> minStack = new Stack<>();

        public MinStack() {

        }

        public void push(int val) {
            stack.push(val);
            if(minStack.empty()) {
                minStack.push(val);
            }else{
                int x = minStack.peek();
                if(val <= x) {
                    minStack.push(val);
                }
            }
        }

        public void pop() {
            int x = stack.pop();
            if(x == minStack.peek()){
                minStack.pop();
            }
        }

        public int top() {
            return stack.peek();
        }

        public int getMin() {
            return minStack.peek();
        }
    }
    class MyQueue {

        private Stack<Integer> s1;
        private Stack<Integer> s2;

        public MyQueue() {
            s1 = new Stack<>();
            s2 = new Stack<>();
        }

        public void push(int x) {
            s1.push(x);//指定push到第一个栈里面
        }

        public int pop() {
            if(empty()) return -1;
            if(s2.empty()) {
                while(!s1.empty()) {
                    s2.push(s1.pop());
                }
            }
            return s2.pop();
        }

        public int peek() {
            if(empty()) return -1;
            if(s2.empty()) {
                while(!s1.empty()) {
                    s2.push(s1.pop());
                }
            }
            return s2.peek();
        }

        public boolean empty() {
            return s1.empty() && s2.empty();
        }
    }

    class MyStack {

        private Queue<Integer> qu1 = new LinkedList<>();
        private Queue<Integer> qu2 = new LinkedList<>();

        public MyStack() {

        }
        /**
         入栈
         */
        public void push(int x) {
            if(!qu1.isEmpty()){
                qu1.offer(x);
            }else if(!qu2.isEmpty()){
                qu2.offer(x);
            }else{
                qu1.offer(x);
            }
        }
        /**
         出栈
         */
        public int pop() {
            if(empty()) {
                return -1;
            }
            int e = -1;
            if(!qu1.isEmpty()) {
                int size = qu1.size();
                for(int i = 0;i < size-1;i++){
                    e = qu1.poll();
                    qu2.offer(e);
                }
                e = qu1.poll();
            }else{
                int size = qu2.size();
                for(int i = 0;i < size-1;i++){
                    e = qu2.poll();
                    qu1.offer(e);
                }
                e = qu2.poll();
            }
            return e;
        }
        /**
         得到栈顶元素，不删除
         */
        public int top() {
            if(empty()) {
                return -1;
            }
            int e = -1;
            if(!qu1.isEmpty()) {
                int size = qu1.size();
                for(int i = 0;i < size;i++){
                    e = qu1.poll();
                    qu2.offer(e);
                }
            }else{
                int size = qu2.size();
                for(int i = 0;i < size;i++){
                    e = qu2.poll();
                    qu1.offer(e);
                }
            }
            return e;
        }

        public boolean empty() {
            return qu1.isEmpty() && qu2.isEmpty();
        }
    }
    public class TestDemo {
        public boolean isValid(String s) {
            if(s == null) {
                return false;
            }
            if(s.length() == 0) {
                return true;
            }

            Stack<Character> stack = new Stack<>();
            for(int i = 0;i < s.length();i++) {
                char ch = s.charAt(i);
                if(ch == '{' || ch == '(' || ch == '[') {
                    stack.push(ch);
                }else{
                    //遇到右括号了
                    if(stack.empty()) {
                        System.out.println("右括号多！");
                        return false;
                    }
                    //栈不为空：获取栈顶元素，查看是否匹配
                    char tmp = stack.peek();//[
                    if(tmp == '{' && ch == '}' || tmp == '[' && ch == ']' || tmp == '(' && ch == ')' ) {
                        stack.pop();
                    }else{
                        System.out.println("左右括号顺序不匹配！");
                        return false;
                    }
                }
            }
            if(!stack.empty()) {
                System.out.println("左括号多！");
                return false;
            }
            return true;
        }


    }
}
